package bintree.leetcode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 使用层序遍历判断树是否是对称的树
 * @author yuisama
 * @date 2022/05/13 19:27
 **/
public class Num101_SymmetricTreeNonRecursion {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root.left);
        queue.offer(root.right);
        while (!queue.isEmpty()) {
            TreeNode t1 = queue.poll();
            TreeNode t2 = queue.poll();
            if (t1 == null && t2 == null) {
                continue;
            }
            if (t1 == null || t2 == null) {
                // 找到反例
                return false;
            }
            if (t1.val != t2.val) {
                // 找到反例
                return false;
            }
            // 继续t1.left t2.right入队
            queue.offer(t1.left);
            queue.offer(t2.right);
            // 继续t1.right t2.left
            queue.offer(t1.right);
            queue.offer(t2.left);
        }
        return true;
    }
}